import common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 104. Construct Binary Tree from Inorder and Postorder Traversal
 * 从中序与后序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
class ConstructBinaryTreeFromInorderAndPostorderTraversal {
    int post_idx;
    int[] postorder;
    int[] inorder;
    Map<Integer, Integer> dic = new HashMap<>();

    /**
     * 方法：递归构建二叉树
     * 
     * Args:
     *   inorder: 中序遍历序列
     *   postorder: 后序遍历序列
     * 
     * Returns:
     *   构建的二叉树根节点
     * 
     * Time: O(n) - 遍历每个节点一次
     * 
     * Space: O(n) - 存储中序遍历节点位置的哈希表需要O(n)空间
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        this.inorder = inorder;
        post_idx= postorder.length - 1;
        for(int i = 0; i < inorder.length; i++){
            dic.put(inorder[i], i);
        }
        return recur(0, inorder.length - 1);
    }

    private TreeNode recur(int in_left, int in_right){
        if(in_left > in_right){
            return null;
        }
        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode(root_val);

        int index = dic.get(root_val);

        post_idx--;

        root.right = recur(index + 1, in_right);
        root.left = recur(in_left, index - 1);
        return root;
    }
}